#!/usr/bin/python3
import sys
import time as timepkg
from collections import deque

moves = {'>': (1, 0), 'v': (0, 1), '<': (-1, 0), '^': (0, -1)}

def print_grid(blizzards, positions, width, height, start, goal):
    for y in range(height):
        for x in range(width):
            if (x == 0 or y == 0 or x == width - 1 or y == height - 1) and not ((x, y) == start or (x, y) == goal):
                print('#', end='')
            elif (x, y) in positions:
                print('E', end='')
            else:
                is_blizzard = [0 for i in range(4)]
                is_blizzard[0] = ('>', x, y) in blizzards
                is_blizzard[1] = ('v', x, y) in blizzards
                is_blizzard[2] = ('<', x, y) in blizzards
                is_blizzard[3] = ('^', x, y) in blizzards
                if sum(is_blizzard) > 1:
                    print('+', end='')
                elif ('>', x, y) in blizzards:
                    print('>', end='')
                elif ('v', x, y) in blizzards:
                    print('v', end='')
                elif ('<', x, y) in blizzards:
                    print('<', end='')
                elif ('^', x, y) in blizzards:
                    print('^', end='')
                else:
                    print('.', end='')
        print()
    print()

def parse_input():
    blizzards = set()
    width = height = 0

    for line in sys.stdin:
        stripped = line.strip()
        if len(stripped) == 0: continue
        [blizzards.add((stripped[x], x, height)) for x in range(len(stripped)) if stripped[x] in ('>', '<', '^', 'v')]
        width = max(width, len(stripped))
        height += 1

    print(blizzards, width, height)
    return blizzards, width, height

def simulate_blizzards(blizzards, width, height):
    new_blizzards = set()
    # move blizzards
    for blizzard in blizzards:
        direction, x, y = blizzard
        #print(direction, x, y, '-> ', end='')
        mx, my = moves[direction]
        x += mx
        y += my
        #print(direction, x, y, '-> ', end='')
        x = width - 2 if x == 0 else 1 if x == width - 1 else x
        y = height - 2 if y == 0 else 1 if y == height - 1 else y
        new_blizzards.add((direction, x, y))
        #print(direction, x, y)
    return new_blizzards

def find_goal(blizzards, width, height, start, goal, visualize=False):
    time = 0
    positions = deque([start])

    while True:
        # visualize
        if visualize:
            # scale wait time to account for longer computation
            timepkg.sleep((500 - time) / 5000)
            print("\033c", end='')
            print(f'time is {time}')
            print_grid(blizzards, positions, width, height, start, goal)

        # move blizzards
        blizzards = simulate_blizzards(blizzards, width, height)

        new_positions = deque()
        for position in positions:
            # consider options and add new positions
            x, y = position
            options = [(x, y), (x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)]
            for option in options:
                ox, oy = option
                if option in new_positions:
                    continue
                if option == goal:
                    # move blizzards
                    print(f'found goal in {time + 1} minutes')
                    if visualize:
                        timepkg.sleep(3)
                    return blizzards, time + 1
                if (ox < 1 or oy < 1 or ox > width - 2 or oy > height - 2) and option != start:
                    continue
                if ('>', ox, oy) in blizzards or ('v', ox, oy) in blizzards or ('<', ox, oy) in blizzards or ('^', ox, oy) in blizzards:
                    continue
                new_positions.append(option)
        positions.clear()
        positions = new_positions
        time += 1
        if len(positions) == 0:
            print('error')
            return -1

def tally_time(time, new_time):
    total_time = time + new_time
    print(f'new total time is {total_time} minutes')
    return total_time

def solution(back_and_forth=False, visualize=False):
    total_time = 0
    blizzards, width, height = parse_input()
    start = (1, 0)
    goal = (width - 2, height - 1)

    # from start to finish
    blizzards, time = find_goal(blizzards, width, height, start, goal, visualize=visualize)
    total_time = tally_time(total_time, time)
    if not back_and_forth: return

    # from finish to start
    blizzards, time = find_goal(blizzards, width, height, goal, start, visualize=visualize)
    total_time = tally_time(total_time, time)

    # from start to finish
    blizzards, time = find_goal(blizzards, width, height, start, goal, visualize=visualize)
    total_time = tally_time(total_time, time)

if sys.argv[1] in '1':
    solution(visualize=True)
else:
    solution(back_and_forth=True, visualize=True)
